"""
数据结构：如何在计算机的内存中表示数据（存储数据）
    ~ 线性结构：元组（tuple）、列表（list）、栈（stack）、队列（queue）、串（str）
        - 栈：FILO（先进后出）
            ~ 检查表达式中的括号是否匹配
            ~ 中缀表达式变成逆波兰表达式
            ~ 逆波兰表达式（后缀表达式）求值
            ~ 面试题：有五个元素，入栈的顺序是1、2、3、4、5，写出所有可能的出栈顺序 ---> 卡特兰数
        - 队列：FIFO（先进先出）
    ~ 非线性结构：树、堆、图
    ~ 离散结构：set / dict ---> 哈希（散列）存储
算法：解决问题的步骤（方法） ---> 如何操作数据得到想要的结果
"""
import operator


class Stack:
    """栈（先进后出）"""

    def __init__(self):
        self.elems = []
    
    def push(self, elem):
        """入栈"""
        self.elems.append(elem)
    
    def pop(self):
        """出栈"""
        return self.elems.pop()
    
    @property
    def is_empty(self):
        """检查栈是否为空"""
        return len(self.elems) == 0


def eval_suffix(expr):
    """逆波兰表达式求值
    :returns: 返回表达式求值的结果
    """
    operators = {
        '+': operator.add,
        '-': lambda x, y: x - y,
        '*': float.__mul__,
        '/': float.__truediv__
    }
    stack = Stack()
    for item in expr.split():
        if item.isdigit():
            stack.push(float(item))
        else:
            num2 = stack.pop()
            num1 = stack.pop()
            stack.push(operators[item](num1, num2))
    return stack.pop()


def check_bracket(expr):
    """检查表达式中的括号是否匹配
    :returns: 括号完全匹配返回True, 否则返回False
    """
    stack = Stack()
    for ch in expr:
        if ch in ('(', '[', '{'):
            stack.push(ch)
        elif ch in (')', ']', '}'):
            if not stack.is_empty:
                left = stack.pop()
                if not (left == '(' and ch == ')' or\
                    left == '[' and ch == ']' or\
                    left == '{' and ch == '}'):
                    return False
            else:
                return False
    return stack.is_empty


# print(eval_suffix('2 3 + 5 *'))
# print(eval_suffix('5 2 3 + *'))
# print(eval_suffix('10 2 3 + 1 - *'))
# print(check_bracket('(2 + 3) * 5'))
# print(check_bracket('((2 + 3) * 5'))
# print(check_bracket('[10 * (2 + 3} - 1]'))
# print(check_bracket('[10 * {(2 + 3)} - 1]'))
# print(check_bracket('(2 + 3] * 5'))
